/*
 * @FilePath: /data-and-structure-lv/18/b-tree.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2022-01-08 10:54:04
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2022-01-09 18:19:15
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define T 3
#define MAX_T(t) (2 * t - 1)
#define MIN_T(t) (t - 1)

typedef int ElementType;

typedef struct BtreeNodeTag
{
    int size;
    int n;
    ElementType *key;
    struct BtreeNodeTag **c;
    int leaf;
} BtreeNode;

typedef struct BTreeTag
{
    BtreeNode *root;
} Btree;

typedef struct BtreeSearchResultTag
{
    BtreeNode *x;
    int i;
} BtreeSearchResult;

BtreeSearchResult *b_tree_search(BtreeNode *x, ElementType k)
{
    int i = 1;
    while (i <= x->n && k > x->key[i])
    {
        /* code */
        i++;
    }
    if (i <= x->n && k == x->key[i])
    {
        BtreeSearchResult *bsr = malloc(sizeof(BtreeSearchResult));
        bsr->i = i;
        bsr->x = x;
        return bsr;
    }
    else if (x->leaf)
    {
        return NULL;
    }
    else
    {
        return b_tree_search(x->c[i], k);
    }
}

ElementType *create_key(int size)
{
    ElementType *k = malloc(sizeof(ElementType) * size + 1);
    k[0] = INT_MIN;
    for (int i = 1; i <= size; i++)
    {
        k[i] = INT_MAX;
    }
    return k;
}

BtreeNode **create_child(int size)
{
    BtreeNode **c = malloc(sizeof(BtreeNode *) * size + 1 + 1);
    for (int i = 0; i <= size + 1; i++)
    {
        c[i] = NULL;
    }
    return c;
}

BtreeNode *create_btree_node()
{
    BtreeNode *new_b_tree_node = malloc(sizeof(BtreeNode));
    ElementType *k = create_key(MAX_T(T));
    BtreeNode **c = create_child(MAX_T(T));
    new_b_tree_node->key = k;
    new_b_tree_node->c = c;
    new_b_tree_node->leaf = 0;
    new_b_tree_node->size = MAX_T(T);
    new_b_tree_node->n = 0;
    return new_b_tree_node;
}

BtreeNode *init(BtreeNode *root)
{
    if (root == NULL)
    {
        root = create_btree_node();
    }
    root->key[1] = 'G';
    root->key[2] = 'M';
    root->key[3] = 'P';
    root->key[4] = 'X';
    root->n = 4;
    root->leaf = 0;

    BtreeNode *c1 = create_btree_node();
    c1->key[1] = 'A';
    c1->key[2] = 'C';
    c1->key[3] = 'D';
    c1->key[4] = 'E';
    c1->n = 4;
    c1->leaf = 1;

    BtreeNode *c2 = create_btree_node();
    c2->key[1] = 'J';
    c2->key[2] = 'K';
    c2->n = 2;
    c2->leaf = 1;

    BtreeNode *c3 = create_btree_node();
    c3->key[1] = 'N';
    c3->key[2] = 'O';
    c3->n = 2;
    c3->leaf = 1;

    BtreeNode *c4 = create_btree_node();
    c4->key[1] = 'R';
    c4->key[2] = 'S';
    c4->key[3] = 'T';
    c4->key[4] = 'U';
    c4->key[5] = 'V';
    c4->n = 5;
    c4->leaf = 1;

    BtreeNode *c5 = create_btree_node();
    c5->key[1] = 'Y';
    c5->key[2] = 'Z';
    c5->n = 2;
    c5->leaf = 1;

    root->c[1] = c1;
    root->c[2] = c2;
    root->c[3] = c3;
    root->c[4] = c4;
    root->c[5] = c5;
    return root;
}

Btree *b_tree_create(Btree *btree)
{
    BtreeNode *x = create_btree_node();
    x->leaf = 1;
    btree->root = x;
    return btree;
}

void b_tree_split_child(BtreeNode *x, int i)
{
    BtreeNode *z = create_btree_node();
    BtreeNode *y = x->c[i];
    z->leaf = y->leaf;
    z->n = MIN_T(T);
    for (int j = 1; j <= z->n; j++)
    {
        z->key[j] = y->key[j + T];
    }
    if (!y->leaf)
    {
        for (int j = 1; j <= T; j++)
        {
            z->c[j] = y->c[j + T];
        }
    }
    y->n = MIN_T(T);
    for (int j = x->n + 1; j >= i + 1; j--)
    {
        x->c[j + 1] = x->c[j];
    }
    x->c[i + 1] = z;
    for (int j = x->n; j >= i; j--)
    {
        x->key[j + 1] = x->key[j];
    }
    x->key[i] = y->key[T];
    x->n++;
}

void b_tree_insert_nonfull(BtreeNode *x, ElementType k)
{
    int i = x->n;
    if (x->leaf)
    {
        while (i >= 1 && k < x->key[i])
        {
            x->key[i + 1] = x->key[i];
            i--;
        }
        x->key[i + 1] = k;
        x->n++;
    }
    else
    {
        while (i >= 1 && k < x->key[i])
        {
            i--;
        }
        i++;
        if (x->c[i]->n == MAX_T(T))
        {
            b_tree_split_child(x, i);
            if (k > x->key[i])
            {
                i++;
            }
        }
        b_tree_insert_nonfull(x->c[i], k);
    }
}

void b_tree_insert(Btree *btree, ElementType k)
{
    BtreeNode *r = btree->root;
    if (r->n == MAX_T(T))
    {
        BtreeNode *s = create_btree_node();
        btree->root = s;
        s->leaf = 0;
        s->n = 0;
        s->c[1] = r;
        b_tree_split_child(s, 1);
        b_tree_insert_nonfull(s, k);
    }
    else
    {
        b_tree_insert_nonfull(r, k);
    }
}

ElementType find_min(Btree *btree)
{
    BtreeNode *r = btree->root;
    if (r->n == 0)
    {
        return -1;
    }
    BtreeNode *y = r->c[1];
    while (y->c[1] != NULL)
    {
        y = y->c[1];
    }
    return y->key[1];
}

void print_btree_search_result(BtreeSearchResult *bsr, ElementType k)
{
    if (bsr != NULL)
    {
        printf("key:%c BtreeSearchResult: n:%d leaf:%d i:%d key:[", k, bsr->x->n, bsr->x->leaf, bsr->i);
        for (int i = 1; i <= bsr->x->n; i++)
        {
            printf("%c,", bsr->x->key[i]);
        }
        printf("]\n");
    }
    else
    {
        printf("key:%c is not exists\n", k);
    }
}

void merge(BtreeNode *y, ElementType k, BtreeNode *z)
{
    int q, i;
    q = i = y->n + 1;
    y->key[i] = k;
    y->n++;
    i++;
    int j = z->n;
    for (int p = 1; p <= j; p++)
    {
        y->key[i] = z->key[p];
        i++;
    }
    if (!y->leaf)
    {
        q++;
        for (int p = 1; p <= j + 1; p++)
        {
            y->c[q] = z->c[p];
            q++;
        }
    }
    y->n = y->n + z->n;
}

void delete_child(BtreeNode *x, int i)
{
    int j = i;
    while (j < x->n + 1)
    {
        x->c[j] = x->c[j + 1];
        j++;
    }
    x->c[j] = NULL;
}

void delete_key(BtreeNode *x, int i)
{
    int j = i;
    while (j < x->n)
    {
        x->key[j] = x->key[j + 1];
        j++;
    }
    x->key[j] = INT_MAX;
}

void down_delete(BtreeNode *y, int i);

void down_b_tree_delete(BtreeNode *x, ElementType k)
{
    int i = x->n;
    while (i >= 1 && k < x->key[i])
    {
        i--;
    }
    if (k == x->key[i])
    {
        down_delete(x, i);
    }
    else if (!x->leaf)
    {
        i++;
        BtreeNode *z = x->c[i];
        down_b_tree_delete(z, k);
    }
    else
    {
        printf("key:%c is not exits\n", k);
    }
}

void down_delete(BtreeNode *y, int i)
{
    if (y->leaf)
    {
        delete_key(y, i);
        y->n--;
    }
    else
    {
        BtreeNode *u = y->c[i];
        int p = u->n;
        BtreeNode *v = y->c[i + 1];
        int q = v->n;
        if (p >= T)
        {
            y->key[i] = u->key[p];
            down_delete(u, p);
        }
        else if (q >= T)
        {
            y->key[i] = v->key[1];
            down_delete(v, q);
        }
        else
        {
            merge(u, y->key[i], v);
            ElementType k = y->key[i];
            delete_key(y, i);
            delete_child(y, i + 1);
            y->n--;
            down_b_tree_delete(u, k);
        }
    }
}

void b_tree_delete(Btree *btree, ElementType k)
{
    BtreeNode *r = btree->root;
    if (r->n == 1 && r->c[1]->n == MIN_T(T) && r->c[2]->n == MIN_T(T))
    {
        /* code */
        BtreeNode *y = r->c[1];
        BtreeNode *z = r->c[2];
        merge(y, r->key[1], z);
        btree->root = y;
    }
    down_b_tree_delete(r, k);
}

void delete_init(BtreeNode *root)
{
    root->key[1] = 'P';
    root->n = 1;
    root->leaf = 0;

    BtreeNode *c1 = create_btree_node();
    c1->key[1] = 'C';
    c1->key[2] = 'G';
    c1->key[3] = 'M';
    c1->n = 3;
    c1->leaf = 0;

    BtreeNode *c2 = create_btree_node();
    c2->key[1] = 'T';
    c2->key[2] = 'X';
    c2->n = 2;
    c2->leaf = 0;

    root->c[1] = c1;
    root->c[2] = c2;

    BtreeNode *c11 = create_btree_node();
    c11->key[1] = 'A';
    c11->key[2] = 'B';
    c11->n = 2;
    c11->leaf = 1;

    BtreeNode *c12 = create_btree_node();
    c12->key[1] = 'D';
    c12->key[2] = 'E';
    c12->key[3] = 'F';
    c12->n = 3;
    c12->leaf = 1;

    BtreeNode *c13 = create_btree_node();
    c13->key[1] = 'J';
    c13->key[2] = 'K';
    c13->key[3] = 'L';
    c13->n = 3;
    c13->leaf = 1;

    BtreeNode *c14 = create_btree_node();
    c14->key[1] = 'N';
    c14->key[2] = 'O';
    c14->n = 2;
    c14->leaf = 1;

    c1->c[1] = c11;
    c1->c[2] = c12;
    c1->c[3] = c13;
    c1->c[4] = c14;

    BtreeNode *c21 = create_btree_node();
    c21->key[1] = 'Q';
    c21->key[2] = 'R';
    c21->key[3] = 'S';
    c21->n = 3;
    c21->leaf = 1;

    BtreeNode *c22 = create_btree_node();
    c22->key[1] = 'U';
    c22->key[2] = 'V';
    c22->n = 2;
    c22->leaf = 1;

    BtreeNode *c23 = create_btree_node();
    c23->key[1] = 'Y';
    c23->key[2] = 'Z';
    c23->n = 2;
    c23->leaf = 1;

    c2->c[1] = c21;
    c2->c[2] = c22;
    c2->c[3] = c23;
}

void main()
{
    Btree *btree = malloc(sizeof(Btree));
    btree = b_tree_create(btree);
    // init(btree->root);

    // ElementType k = 'F';
    // BtreeSearchResult *bsr = b_tree_search(btree->root, k);
    // print_btree_search_result(bsr, k);

    // k = 'B';
    // b_tree_insert(btree, k);
    // bsr = b_tree_search(btree->root, k);
    // print_btree_search_result(bsr, k);

    // k = 'Q';
    // b_tree_insert(btree, k);
    // bsr = b_tree_search(btree->root, k);
    // print_btree_search_result(bsr, k);

    // k = 'L';
    // b_tree_insert(btree, k);
    // bsr = b_tree_search(btree->root, k);
    // print_btree_search_result(bsr, k);

    // k = 'F';
    // b_tree_insert(btree, k);
    // bsr = b_tree_search(btree->root, k);
    // print_btree_search_result(bsr, k);

    // ElementType key[] = {'F', 'S', 'Q', 'K', 'C', 'L', 'H', 'T', 'V', 'W', 'M', 'R', 'N', 'P', 'A', 'B', 'X', 'Y', 'D', 'Z', 'E'};
    // BtreeSearchResult *bsr;
    // for (int i = 0; i < 21; i++)
    // {
    //     b_tree_insert(btree, key[i]);
    //     bsr = b_tree_search(btree->root, key[i]);
    //     print_btree_search_result(bsr, key[i]);
    // }
    // printf("min:%c\n", find_min(btree));

    // //merge test
    // BtreeNode *y=create_btree_node();
    // BtreeNode *z=create_btree_node();
    // ElementType k='C';
    // y->key[1]='A';
    // y->key[2]='B';
    // y->n=2;
    // z->key[1]='D';
    // z->key[2]='E';
    // z->n=2;
    // merge(y,k,z);

    // BtreeNode *x = create_btree_node();
    // x->key[1] = 'B';
    // x->key[2] = 'C';
    // x->n = 2;
    // BtreeNode *y = create_btree_node();
    // y->key[1] = 'A';
    // y->n = 1;
    // x->c[1] = y;
    // BtreeNode *z = create_btree_node();
    // x->c[2] = z;
    // delete_child(x, 1);
    // delete_key(x, 1);

    delete_init(btree->root);
    ElementType k = 'F';
    BtreeSearchResult *bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    b_tree_delete(btree, k);
    k = 'E';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);

    k = 'M';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'J';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'M';
    b_tree_delete(btree, k);
    k = 'C';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'J';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);

    k = 'G';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'D';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'G';
    b_tree_delete(btree, k);
    k = 'C';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'D';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);

    k = 'P';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'D';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    b_tree_delete(btree, k);
    k = 'P';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'E';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);

    k = 'L';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'B';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    b_tree_delete(btree, k);
    k = 'L';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
    k = 'A';
    bsr = b_tree_search(btree->root, k);
    print_btree_search_result(bsr, k);
}
